"""
# Definition for a Node.
"""
from typing import *


class Node:

    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child


class Solution:

    def flatten(self, head: 'Node') -> 'Node':

        def f(node: 'Node') -> List['Node']:
            h, t, p = node, node, node
            while p:
                if p.child is not None:
                    ch, ct = f(p.child)
                    p.child = None
                    tmp = p.next
                    p.next = ch
                    ch.prev = p
                    if tmp is not None:
                        ct.next = tmp
                        tmp.prev = ct
                    p = ct
                t = p
                p = p.next
            return [h, t]

        return f(head)[0]